/*  naive_chains.cpp
 * Copyright (C) 2010, Francisco Claude & Patrick Nicholson, all rights reserved.
 *
 * Francisco Claude & Patrick Nicholson <(fclaude|p3nichol)@cs.uwaterloo.ca>
 *
 *   This program is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 */

#include<iostream>
#include<fstream>
#include<sstream>
#include<algorithm>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<cassert>
#include<cmath>
#include<limits>

using namespace std;

#include "naive_chains.h"

NaiveChains::NaiveChains(ifstream & input) {
  totalPoints = 0;
  dminx = dminy = numeric_limits<double>::max();
  dmaxx = dmaxy = numeric_limits<double>::min();
  aminx = aminy = numeric_limits<double>::max();
  amaxx = amaxy = numeric_limits<double>::min();
  input.read((char*)&dchainsLen,sizeof(size_t));
  dlength = new size_t[dchainsLen];
  dchains = new Point*[dchainsLen];
  for(size_t i=0;i<dchainsLen;i++) {
    input.read((char*)&(dlength[i]),sizeof(size_t));
    dchains[i] = new Point[dlength[i]];
    double * tmpArr = new double[2*dlength[i]];
    input.read((char*)tmpArr,sizeof(double)*2*dlength[i]);
    for(size_t j=0;j<dlength[i];j++) {
      dchains[i][j].setX(tmpArr[2*j]);
      dchains[i][j].setY(tmpArr[2*j+1]);
      if(j!=0 && j!=dlength[i]-1) {
        dminy = min(dminy,tmpArr[2*j+1]);
        dmaxy = max(dmaxy,tmpArr[2*j+1]);
        dminx = min(dminx,tmpArr[2*j]);
        dmaxx = max(dmaxx,tmpArr[2*j]);
      }
    }
    totalPoints += dlength[i]-2;
    delete [] tmpArr;
  }
  input.read((char*)&achainsLen,sizeof(size_t));
  alength = new size_t[achainsLen];
  achains = new Point*[achainsLen];
  for(size_t i=0;i<achainsLen;i++) {
    input.read((char*)&(alength[i]),sizeof(size_t));
    achains[i] = new Point[alength[i]];
    double * tmpArr = new double[2*alength[i]];
    input.read((char*)tmpArr,sizeof(double)*2*alength[i]);
    for(size_t j=0;j<alength[i];j++) {
      achains[i][j].setX(tmpArr[2*j]);
      achains[i][j].setY(tmpArr[2*j+1]);
      if(j!=0 && j!=alength[i]-1) {
        aminy = min(aminy,tmpArr[2*j+1]);
        amaxy = max(amaxy,tmpArr[2*j+1]);
        aminx = min(aminx,tmpArr[2*j]);
        amaxx = max(amaxx,tmpArr[2*j]);
      }
    }
    totalPoints += alength[i]-2;
    delete [] tmpArr;
  }
  cout << "Total Ascending chains  : " << achainsLen << endl;
  cout << "Total Descending chains : " << dchainsLen << endl;
}

NaiveChains::~NaiveChains() {
  for(size_t i=0;i<dchainsLen;i++) {
    delete [] dchains[i];
  }
  delete [] dlength;
  delete [] dchains;
  for(size_t i=0;i<achainsLen;i++) {
    delete [] achains[i];
  }
  delete [] alength;
  delete [] achains;
}

double NaiveChains::getAvgNumPointsPerChain() const {
  return ((double)totalPoints) / (dchainsLen + achainsLen);
}

double NaiveChains::getStdDevOfPointsPerChain() const {
  double avg = getAvgNumPointsPerChain();
  double stddev = 0;
  for (size_t i = 0; i < dchainsLen; i++) {
    stddev += (dlength[i] - avg) * (dlength[i] - avg);
  }

  for (size_t i = 0; i < achainsLen; i++) {
    stddev += (alength[i] - avg) * (alength[i] - avg);
  }
  stddev /= (achainsLen + dchainsLen - 1);
  return sqrt(stddev);
}

size_t NaiveChains::getNumPoints() const {
  return totalPoints;
}

size_t NaiveChains::getNumChains() const {
  return dchainsLen+achainsLen;
}

size_t NaiveChains::getSize() const {
  return sizeof(Point)*(getNumChains()+getNumPoints())
          +sizeof(size_t)*(1+getNumChains())
          +sizeof(Point*)*(getNumChains())
          +sizeof(NaiveChains);
}

vector<Point> NaiveChains::search(const Point & p1, const Point & p2) const {
  Point p1d(max(dminx,p1.getX()),max(dminy,p1.getY()));
  Point p2d(min(dmaxx,p2.getX()),min(dmaxy,p2.getY()));
  vector<Point> ret;
  for(size_t i=0;i<dchainsLen;i++)
    searchChainHitsDes(ret,dchains[i],p1d,p2d,dlength[i]);
  Point p1a(max(aminx,-p2.getX()),max(aminy,p1.getY()));
  Point p2a(min(amaxx,-p1.getX()),min(amaxy,p2.getY()));
  for(size_t i=0;i<achainsLen;i++)
    searchChainHitsDes(ret,achains[i],p1a,p2a,alength[i]);
  return ret;
}

vector<Point> NaiveChains::naiveSearch(const Point & p1, const Point & p2) const {
  vector<Point> ret;
  Point p1d(max(dminx,p1.getX()),max(dminy,p1.getY()));
  Point p2d(min(dmaxx,p2.getX()),min(dmaxy,p2.getY()));
  for(size_t i=0;i<dchainsLen;i++) {
    for(size_t j=1;j<dlength[i]-1;j++) {
      if(inside(dchains[i][j],p1d,p2d)) {
        ret.push_back(dchains[i][j]);
      }
    }
  }

  Point p1a(max(aminx,-p2.getX()),max(aminy,p1.getY()));
  Point p2a(min(amaxx,-p1.getX()),min(amaxy,p2.getY()));
  for(size_t i=0;i<achainsLen;i++) {
    for(size_t j=1;j<alength[i]-1;j++) {
      if(inside(achains[i][j],p1a,p2a))
        ret.push_back(achains[i][j]);
    }
  }
  return ret;
}

vector<Point> NaiveChains::adaptiveSearch(const Point & p1, const Point & p2) const {
  vector<Point> vec;

  size_t i = 0;
  size_t j = dchainsLen-1;
  
  Point p1d(max(dminx,p1.getX()),max(dminy,p1.getY()));
  Point p2d(min(dmaxx,p2.getX()),min(dmaxy,p2.getY()));

  while((i+1)<=(j+1)) {
    size_t m = (i+j)/2;
    size_t res = searchChainCrossDes(vec, dchains[m], p1d, p2d, dlength[m]);
    if(res == RIGHT) {
      j = m-1;
    } else if(res==LEFT) {
      i = m+1;
    } else {
      size_t pos = m+1;
      while(pos<=j) {
        size_t val = searchChainCrossDes(vec, dchains[pos], p1d, p2d, dlength[pos]);
        if(val==LEFT || val==RIGHT) break;
        pos++;
      }
      pos = m-1;
      while(pos+1>=i+1) {
        size_t val = searchChainCrossDes(vec, dchains[pos], p1d, p2d, dlength[pos]);
        if(val==LEFT || val==RIGHT) break;
        pos--;
      }
      break;
    }
  }

  i = 0;
  j = achainsLen-1;
  
  Point p1a(max(aminx,-p2.getX()),max(aminy,p1.getY()));
  Point p2a(min(amaxx,-p1.getX()),min(amaxy,p2.getY()));

  while((i+1)<=(j+1)) {
    size_t m = (i+j)/2;
    size_t res = searchChainCrossDes(vec, achains[m], p1a, p2a, alength[m]);
    if(res == RIGHT) {
      j = m-1;
    } else if(res==LEFT) {
      i = m+1;
    } else {
      size_t pos = m+1;
      while(pos<=j) {
        size_t val = searchChainCrossDes(vec, achains[pos], p1a, p2a, alength[pos]);
        if(val==LEFT || val==RIGHT) break;
        pos++;
      }
      pos = m-1;
      while(pos+1>=i+1) {
        size_t val = searchChainCrossDes(vec, achains[pos], p1a, p2a, alength[pos]);
        if(val==LEFT || val==RIGHT) break;
        pos--;
      }
      break;
    }
  }
  return vec;
}

